#include<stdio.h> 
#include<string.h> 
#include<stdlib.h>
#include "../include/meta.h"
#include "../include/vfs_errorcodes.h"

// inserts node in tree, data to be inserted is string       
bstnode* bst_insert(bstnode *bstroot,char* str, int index) 
      { 	
		 bstnode *temp;
		 bstnode *ptr;		 

		 bstnode *s=(bstnode*)malloc(sizeof(bstnode));
		 strcpy(s->data,str);		 
                 s->left=NULL; 
                 s->right=NULL;	
		 s->index=index;	
	 
                 if(bstroot==NULL)
		 {
		  bstroot=s;	
		  return bstroot;
		 }
				
		 temp=bstroot;
		 ptr=temp;			    
	      
			while(temp)
			{
				//printf("str,temp->data : %s , %s",str,temp->data);

				if(strcmp(str,temp->data)==0) 
				{
									 
				 //printf("BST: Already There Can't enter\n");
			
				 return  bstroot;				
				}		

		        	else if( (temp->right==NULL) && (strcmp(str,temp->data)>0) )
				{
				ptr=temp;
				temp=temp->right;
				temp=s; 
				
				ptr->right=temp;
				
				break;
				}
		
				else if( (temp->right!=NULL) && (strcmp(str,temp->data)>0) ) 
				{
				ptr=temp;
				temp=temp->right; 
				} 

				else if((temp->left==NULL)&&(strcmp(str,temp->data)< 0)) 
				{
				ptr=temp;
				temp=temp->left;
				temp=s; 
				
				ptr->left=temp;
				
				break; 
				}
				 
				else if( (temp->left!=NULL) && (strcmp (str,temp->data)< 0)) 
				{
				ptr=temp;
				temp=temp->left; 
				}						
					
		   }
	 return bstroot;
		
       } 

void displayBstTree(bstnode *bstroot){
	
	if(bstroot!=NULL){
	
	displayBstTree(bstroot->left);

	printf("%s\t",bstroot->data);	
	printf("%d\n",bstroot->index);
	
	displayBstTree(bstroot->right);
	}	
}


//delete the node from given path
bstnode* bst_delete(bstnode *bstroot,char* str) 
      { 
	 	 bstnode *temp,*temp1;
		 bstnode *ptr,*ptrp;	
		 ptr= (bstnode *) malloc(sizeof(bstnode));	

		 temp=bstroot;
          	
           		 if(bstroot==NULL)
				 {			  
				  //printf("BST: No Data is present\n");
				  return NULL;
				 }
				
			 temp=bstroot;
			 ptr=NULL;			    
	      
			 while(temp)				
			 {
				 if(strcmp(str,temp->data)==0 && ptr==NULL)
					{
							if(temp->left && temp->right)
								{
									ptrp=temp;
									temp1=temp->right;
									
									while(temp1->left!= NULL)
									{
										ptrp=temp1;
										temp1=temp1->left;
									}
									
									strcpy(temp->data,temp1->data);
									temp->index=temp1->index;
									
									if(temp1->right != NULL)
									{
										ptrp->left=temp1->right;
										temp1->right=NULL;
										free(temp1);
									}
									
									else
									{
										ptrp->right=NULL;
										free(temp1);
									}
									return bstroot;
									
								}
								
							else if(temp->left==NULL && temp->right==NULL)
								{
									free(temp);
									return NULL;
								}
									
							else if(temp->right==NULL)
								{
									return temp->left;
								}
									
							else if(temp->left==NULL)
									return temp->right;
					}
					
				else if(strcmp(str,temp->data)<0)
					{
						ptr=temp;
						temp=temp->left;
					}
						
				else if(strcmp(str,temp->data)>0)
					{
						ptr=temp;
						temp=temp->right;
					}
					
				else if(strcmp(str,temp->data)==0)
					{
						if(temp->left!= NULL && temp->right!= NULL)
						{
									ptrp=temp;
									temp1=temp->right;
									
									while(temp1->left!= NULL)
									{
										ptrp=temp1;
										temp1=temp1->left;
									}
									
									strcpy(temp->data,temp1->data);
									temp->index=temp1->index;
									
									if(temp1->right != NULL)
									{
										ptrp->left=temp1->right;
										temp1->right=NULL;
										free(temp1);
									}
									
									else
									{
										ptrp->right=NULL;
										free(temp1);
									}
									return bstroot;
						}
						
						else if(temp->left==NULL && temp->right==NULL)
						{
							if(temp==ptr->left)
								ptr->left=NULL;
								
							else
								ptr->right=NULL;
								
							free(temp);
							return bstroot;
						}
						
						else if(temp->left== NULL)
						{
							if(temp==ptr->left)
							{
								ptr->left=temp->right;
							}
							
							else
								ptr->right=temp->right;
								
								temp->right=NULL;
								free(temp);
								return bstroot;
						}
						
						else if(temp->right==NULL)
						{
							if(temp==ptr->left)
							{
								ptr->left=temp->left;
							}
							
							else
								ptr->right=temp->left;
								
								temp->left=NULL;
								free(temp);
								return bstroot;
						}
					}
	 									
					
		  }
	if(temp==NULL)
		{
			//printf("BST: Data is not present in tree\n");
			return bstroot;
		}
					
  }
		 	
void free_bst(bstnode* bstroot)
{	if(bstroot!=NULL){
		//free_bst(bstroot->left);
		free_bst(bstroot->right);
		//free(bstroot);
	}
}

int bst_search(bstnode *bstroot,char* str) 
      { 
	bstnode *temp;
	temp=bstroot;

	if(bstroot==NULL)
		return -1;		
	      
			 while(temp)
			  {
				//if path is found
				if(strcmp(str,temp->data)==0) 
				  return temp->index;
								

					else if (strcmp(str,temp->data)>0)
						temp=temp->right;
	
					else if(strcmp(str,temp->data)<0)
						temp=temp->left;
			
						 									
					
		           }
		return -1;
	
      }	 



